#include "clist.h"
#include <stdio.h>

Node* headInsert(Node* pHead, int data){
    Node *node = new Node;
    node->data = data;
    node->pNext = pHead;
    
    return node;
}

Node* tailInsert(Node* pHead, int data){
    Node* node = new Node;
    node->data = data;
    node->pNext = NULL;

    if(pHead == NULL){
        pHead = node;
        return pHead;
    }

    Node* p = pHead;
    while(p->pNext != NULL){
        p = p->pNext;
    }

    p->pNext = node;
    return pHead;
}

Node* reverseList(Node* pHead){
    Node* pre = NULL;
    Node* cur = pHead;
    Node* next = NULL;

    while(cur != NULL){
        next = cur->pNext;
        cur->pNext = pre;
        pre = cur;
        cur = next; 
    }

    return pre;
}

Node* delListNode(Node* pHead, int data){
    Node* p = pHead;
    Node* q = NULL;

    while(p != NULL){
        if(p->data == data){
            q->pNext = p->pNext;
            delete p;
            break;
        }

        q = p;
        p = p->pNext;
    }

    return pHead;
}


void printList(Node* pHead){
    Node* p = pHead;

    printf("list data: ");
    while(p != NULL){
        printf("%d ", p->data);
        p = p->pNext;
    }
    printf("\n");
}

Node* mergeList(Node* list1, Node* list2){
    Node node;
    Node* p = &node;
    
    Node* p1 = list1;
    Node* p2 = list2;

    while(p1 != NULL && p2 != NULL){
        if(p1->data <= p2->data){
            p->pNext = p1;
            p1 = p1->pNext;
        }else{
            p->pNext = p2;
            p2 = p2->pNext;
        }
        p = p->pNext;
    }

    if(p1 != NULL){
        p->pNext = p1;
    }else{
        p->pNext = p2;
    }

    return node.pNext;
}

// 冒泡排序函数
Node* blblSortList(Node *head) {
    if (head == nullptr || head->pNext == nullptr) {
        return head; // 空链表或单节点链表直接返回
    }
    
    // 添加哑节点简化操作
    Node dummy;
    dummy.pNext = head;
    
    Node *last = nullptr;  // 用于记录已排序部分的结束位置
    bool swapped;           // 标记本轮是否发生交换
    
    do {
        swapped = false;
        Node *prev = &dummy;    // 前驱节点
        Node *cur = prev->pNext; // 当前节点
        
        while (cur->pNext != last) {
            // 比较相邻节点
            if (cur->data > cur->pNext->data) {
                // 交换相邻节点
                Node *nextNode = cur->pNext;
                
                // 更新指针
                prev->pNext = nextNode;
                cur->pNext = nextNode->pNext;
                nextNode->pNext = cur;
                
                swapped = true; // 标记发生交换
                
                // 更新当前指针（因为交换后cur已经后移）
                cur = nextNode;
            }
            
            // 移动到下一对节点
            prev = prev->pNext;
            cur = cur->pNext;
        }
        
        // 设置本轮排序的结束位置
        last = cur;
        
    } while (swapped); // 如果本轮发生交换则继续
    
    return dummy.pNext;
}
